from typing import List
class Solution:
    def getWidth(self,num):  #步骤3：求一个数中连续最多的1
        w=0
        while num>0:
            num&=num<<1
            w+=1
        return w
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        nums=[int(''.join(n),base=2) for n in matrix]  #步骤1：每一行当作二进制数
        res,n=0,len(nums)
        for i in range(n):   #步骤2：枚举所有的组合，temp存储相与的结果
            temp=nums[i]
            for j in range(i,n):
                temp&=nums[j]
                w=self.getWidth(temp)
                h=j-i+1
                res=max(res,min(w,h))
        return res*res

# 测试函数
def test_algorithm():
    """测试算法正确性"""
    solution = Solution()
    
    # 测试用例
    test_cases = [
        ([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]], 4),
        ([["0","1"],["1","0"]], 1),
        ([["0"]], 0),
        ([["1"]], 1),
        ([["1","1"],["1","1"]], 4),
    ]
    
    print("221. 最大正方形 - 算法测试")
    print("=" * 40)
    
    for i, (matrix, expected) in enumerate(test_cases, 1):
        result = solution.maximalSquare(matrix)
        status = "✓" if result == expected else "✗"
        
        print(f"测试用例 {i}:")
        print(f"矩阵: {matrix}")
        print(f"期望结果: {expected}")
        print(f"实际结果: {result}")
        print(f"状态: {status}")
        print("-" * 40)

if __name__ == "__main__":
    test_algorithm()
